package algorithms.tree;

import edu.princeton.cs.algs4.Queue;
import org.attoparser.select.NodeSelectorMarkupHandler;

/**
 * @功能
 * @创建时间 2021/1/10
 */
public class  BST<Key extends Comparable<Key>,Value> {
    private Node root;
    private class Node{
        private Key key;
        private Value val;
        private Node left,right;
        private int N;
        public Node(Key key,Value val,int N){
            this.key=key;
            this.val=val;
            this.N=N;
        }
    }
    public int size(){
        return size(root);
    }
    private int size(Node root){
        if(root==null) return 0;
        else return root.N;
    }
    public Value get(Key key){
        return get(root,key);
    }
    public Value get(Node x,Key key){
        if(x==null) return null;
        int cmp=key.compareTo(x.key);
        if(cmp<0) return get(x.left,key);
        else if(cmp>0) return get(x.right,key);
        else return x.val;
    }
    public void put(Key key,Value val){
        root=put(root,key,val);
    }
    private Node put(Node x,Key key,Value val){
        if(x==null) return new Node(key,val,1);
        int cmp=key.compareTo(x.key);
        if(cmp<0) x.left=put(x.left,key,val);
        else if(cmp>0) x.right=put(x.right,key,val);
        else x.val=val;
        x.N=size(x.left)+size(x.right)+1;
        return x;
    }
    public Key min(){
        return min(root).key;
    }
    private Node min(Node x){
        if(x.left == null) return x;
        return min(x.left);
    }
    public Key max(){
        return max(root).key;
    }

    private Node max(Node x){
        if(x.right==null) return x;
        else return min(x.right);
    }
    public Key floor(Key key){
        Node x = floor(root,key);
        if(x==null) return null;
        return x.key;
    }

    /**
     *递归查找key，相对较小就往左递归，较大就往右递归
     * @param x
     * @param key
     * @return
     */
    private Node floor(Node x ,Key key){
        if(x==null) return null;
        int cmp=key.compareTo(x.key);
        if(cmp==0) return x;
        if(cmp==0) return floor(x.left,key);
        Node t = floor(x.right,key);
        if(t!=null) return t;
        else return x;
    }

    public Key select(int k){
        return select(root,k).key;
    }

    /**
     * 返回排名为k的节点，实际比较N递归
     * @param x
     * @param k
     * @return
     */
    private Node select(Node x,int k){
        if(x==null) return null;
        int t=size(x.left);
        if(t>k) return select(x.left,k);
        else if(t<k)return select(x.right,k-t-1);
        else return x;
    }

    public int rank(Key key){
        return rank(key,root);
    }

    /**
     *递归返回小于输入键的节点数量
     * @param key
     * @param x
     * @return
     */
    private int rank(Key key,Node x){
        if(x==null) return 0;
        int cmp=key.compareTo(x.key);
        if(cmp<0)     return rank(key,x.left);
        else if(cmp>0)return 1+size(x.left)+rank(key,x.right);
        else return size(x.left);
    }

    public void deleteMin(){
        root = deleteMin(root);
        System.out.println(root.val);
    }

    /**
     * 找左节点并把当前节点替换为倒数第二个左节点
     * @param x
     * @return
     */
    private Node deleteMin(Node x){
        if(x.left==null) return x.right;
        x.left=deleteMin(x.left);
        x.N=size(x.left)+size(x.right)+1;
        System.out.println(x.val);
        return x;
    }

    public void delete(Key key){
        root = delete(root,key);
    }

    private Node delete(Node x,Key key){
        if(x==null) return null;
        int cmp = key.compareTo(x.key);
        if(cmp<0) x.left=delete(x.left,key);
        else if(cmp>0) x.right=delete(x.right,key);
        else {
            if(x.right==null) return x.left;
            if(x.left==null) x.right=delete(x.right,key);
            Node t=x;
            x=min(t.right);
            x.right=deleteMin(t.right);
            x.left=t.left;
        }
        x.N=size(x.left)+size(x.right)+1;
        return x;
    }

    public Iterable<Key> keys(){
        return keys(min(),max());
    }

    public Iterable<Key> keys(Key lo,Key hi){
        Queue<Key> queue = new Queue<Key>();
        keys(root,queue,lo,hi);
        return queue;
    }

    private void keys(Node x,Queue<Key> queue,Key lo,Key hi){
        if(x==null) return;
        int cmplo=lo.compareTo(x.key);
        int cmphi=hi.compareTo(x.key);
        if(cmplo<0)keys(x.left,queue,lo,hi);
        if(cmplo<=0&&cmphi>=0) queue.enqueue(x.key);
        if(cmphi>0) keys(x.right,queue,lo,hi);
    }


}
class client{
    public static void main(String[] args) {
        BST b =new BST<>();

        b.put( 3,3);

        b.put( 2,2);
        b.put( 1,1);
        b.deleteMin();

        ok:
        for(int i=0;i<10;i++)
        {
for(int j=0;j<10;j++)
{
System.out.println("i=" + i + ",j="+ j);
if(j == 5) break ok;
 }
        }
    }


}
